1. Field of the Invention
This invention relates to caches in microprocessor systems and, more particularly, to the revalidation of virtual tags after memory mapping changes.
2. Description of the Relevant Art
Microprocessors utilize caches to provide faster access to data stored in memory. Caches are typically smaller and faster memory devices that store the most recently accessed blocks of data. Because memory accesses are typically made to memory locations in close proximity to previously accessed memory locations, storing the most recently accessed blocks of data significantly reduces the number of accesses to the system memory.
Virtual addresses in a microprocessor must be translated to physical addresses prior to memory accesses. Likewise, caches that reference data blocks using physical addresses must convert virtual addresses to physical addresses before detecting a cache hit. Rather than translating a virtual address each time it is accessed, a translation lookaside buffer (TLB) stores the most recently accessed virtual-to-physical address translations.
The use of virtual address tags in a cache provides faster and simpler access to data blocks stored in cache. Virtual tags eliminate the need to perform a TLB look-up prior to detecting a cache hit. Although a TLB look-up can be done in parallel with cache access, increasing the number of TLB look-ups requires a larger TLB to minimize TLB misses. It is advantageous to keep the TLB small enough to avoid impacting the memory access time. Large TLB's in aggressive clock rate processors typically force a hierarchical TLB structure that adds further complications. The use of virtual tags in a cache greatly reduces the demand on the TLB because the TLB only needs to be referenced on cache misses. In virtual tag caches, the demand for the TLB may be sufficiently low to allow one TLB to services two caches, e.g., an instruction cache and a data cache.
The main drawback of using virtual tags in a cache is that the tags must be invalidated whenever a virtual-to-physical memory mapping change occurs. Although mapping changes typically involve little if any of the data stored in the cache, the tags must be invalidated. The chance exists that one or more virtual tags are remapped to a different physical location. An access to a virtual tag that has been remapped would yield the wrong data.
Invalidating the virtual tags of a cache effectively empties the cache. All data blocks must be re-fetched from memory according to the new mapping, even though many cache entries still have valid virtual tags. Therefore, many of the existing blocks in cache are re-fetched and re-loaded into the cache.
Processors which support write-back caching and maintain coherency with physical memory must typically store physical tags for each cache entry. The physical tags are required for snooping and provide the proper memory address on a write-back. Each physical tag is associated with a cache entry and a virtual tag.
The presence of the physical tags can be used to avoid the unnecessary re-loading of the cache when a memory mapping change occurs. When a cache miss occurs due to an invalidated virtual tag, the TLB is referenced to translate the virtual address of the requested data to a physical address. The physical address from the TLB is checked against the physical tag associated with the invalidated virtual tag. If the physical tag matches the physical address from the TLB, the virtual tag is still valid and the requested data block resides in cache. Because the data block is already in cache, there is no need to refetch the data from memory. The data is read from cache and the virtual tag is revalidated by asserting a valid bit of the virtual tag. This recovery mechanism reduces cache misses and system memory accesses.
The above described recovery mechanism causes a flurry of TLB accesses when a virtual-to-physical memory mapping change occurs (i.e. a remapping occurs). A remapping invalidates all the virtual tags, which effectively empties the cache. Because the TLB is accessed on each cache miss, a remapping causes a short term high demand on the TLB accesses. During these periods of high demand on the TLB, the TLB can create a bottleneck that slows down the recovery from the remapping. What is desired is a way to reduce the number of TLB accesses during a virtual-to-physical memory mapping recovery.